import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/*
 * @lc app=leetcode.cn id=51 lang=java
 *
 * [51] N皇后
 *
 * https://leetcode-cn.com/problems/n-queens/description/
 *
 * algorithms
 * Hard (65.97%)
 * Likes:    246
 * Dislikes: 0
 * Total Accepted:    16.7K
 * Total Submissions: 25.2K
 * Testcase Example:  '4'
 *
 * n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 *
 *
 * 上图为 8 皇后问题的一种解法。
 *
 * 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
 *
 * 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 *
 * 示例:
 *
 * 输入: 4
 * 输出: [
 * ⁠[".Q..",  // 解法 1
 * ⁠ "...Q",
 * ⁠ "Q...",
 * ⁠ "..Q."],
 *
 * ⁠["..Q.",  // 解法 2
 * ⁠ "Q...",
 * ⁠ "...Q",
 * ⁠ ".Q.."]
 * ]
 * 解释: 4 皇后问题存在两个不同的解法。
 *
 *
 */

// @lc code=start
class Solution {

    boolean[] row;
    boolean[] col;
    Set<Integer> line1;
    Set<Integer> line2;

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        List<String> cur = new ArrayList<>();
        this.row = new boolean[n];
        this.col = new boolean[n];
        this.line1 = new HashSet<>();
        this.line2 = new HashSet<>();
        Arrays.fill(row, true);
        Arrays.fill(col, true);
        dfs(result, cur, n, 0);
        return result;
    }

    void dfs(List<List<String>> result, List<String> cur,
            int n, int row) {
        if (row==n) {
            result.add(new ArrayList<>(cur));
            return;
        }
        for(int col=0; col < n; col++) {
            if(canPut(row, col)) {
                StringBuilder sb = new StringBuilder();
                for(int i=0; i<n; i++) {
                    if(i == col) {
                        sb.append("Q");
                    } else {
                        sb.append(".");
                    }
                }
                cur.add(sb.toString());
                put(row, col);
                dfs(result, cur, n, row+1);
                get(row, col);
                cur.remove(cur.size()-1);
            }
        }
    }

    boolean canPut(int row, int col) {
        return this.row[row] && this.col[col] &&
                !line1.contains(row+col) && !line2.contains(row-col);
    }

    void put(int row, int col) {
        this.row[row] = false;
        this.col[col] = false;
        this.line1.add(row+col);
        this.line2.add(row-col);
    }

    void get(int row, int col) {
        this.row[row] = true;
        this.col[col] = true;
        this.line1.remove(row+col);
        this.line2.remove(row-col);
    }



}
// @lc code=end

